package practice1_100;

import java.util.Arrays;

public class Practice322 {
    public int coinChange(int[] coins, int amount) {
        int[] dp=new int[amount+1];
        for (int i=0;i< dp.length;i++){
            dp[i]= i+1;
        }
//        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0]=0;
        for (int i=1;i<=amount;i++){
            for (int coin:coins){
                if (i-coin<0) continue;
                dp[i]=Math.min(dp[i-coin]+1,dp[i]);
            }
        }
        if (dp[amount]==amount+1) return -1;
        return dp[amount];
       // return deep(coins,amount,dp);
    }

    public int deep(int[] coins,int amount,int[] dp){
        int res=Integer.MAX_VALUE;
//        if (dp[amount]!=-1)
        if (amount==0)return 0;
        if(amount<0) return -1;
        for (int coin:coins){
            if(amount-coin>=0&&dp[amount-coin]!=-1)
                return dp[amount-coin];
            int subsample= deep(coins,amount-coin,dp);
            if (subsample==-1) continue;
            dp[amount-coin]= Math.min(subsample+1,res) ;

        }
        return dp[amount];
    }


    //做了几个月的题目之后，递归发现看不懂了，怎么回事，😓
    //今天看了看拉不拉东的算法小抄，有了点新的思路
    //譬如，用直接从下至上的方式可能更好理解
    public int coinChange1(int[] coins,int amount){
        //根据小炒上的动态规划问题，第一步，分析出最简单的情况（base case）当amount ==0时候，此时结果为0，无法兑换的情况是-1
        //这个问题的状态，找到amount的状态，就要找amount-1，amount-2，amount-3，amount-4，amount-5...
        //dp[amount] 的结果就是dp[amount-coinI]的值和dp[amount]的谁更小就选谁
        int[] dp=new int[amount+1];//dp数组，用于存储amount的最小值
        for (int i = 1; i < dp.length ; i++) {dp[i]=i+1;}//这个amount 为0，dp[0]=0,其他值dp[amount]=amount+1,代表无限大
        for (int coin:coins) {
            if(dp.length-1>=coin) dp[coin]=1;//恰好刚刚满足情况,此时amount就是1
        }
        for (int i = 1; i < dp.length; i++) {
            for (int coin:coins) {
                if(i-coin>0&&dp[i-coin]<=i-coin)dp[i]=Math.min(dp[i-coin]+1,dp[i]);//i-coin大于0，数组不越界才可，
            }
        }
        return dp[amount]==amount+1?-1:dp[amount];//最终换不了钱，返回-1 否则返回dp[amount]
    }



    public static void main(String[] args) {

        int a=new Practice322().coinChangenew(new int[]{1,2,5,8,9,11},54);
        System.out.println(a);
    }

    //自顶向下法，用递归
    public int coinChangenew(int[] coins, int amount) {
        //弄个记录dp数组，填充数组为dp[amount]=amount+1,代表正无穷
        int[] dp=new int[amount+1];
//        for (int i=0;i<dp.length;i++){
//            dp[i]=Integer.MAX_VALUE;
//        }
        dp[0]=0;//这个代表是金额为0，0种兑换
        int a=change(coins,amount,dp);
        return a;
    }
    public int change(int[] coins, int amount,int[] dp){
        //int sum=0;
        //终止条件
        if(amount<0)return -1;
        if(amount==0) return 0;
        if(dp[amount]!=0) return dp[amount];//先查表

        int min=Integer.MAX_VALUE;
        for (int coin:coins){
            //if(amount-coin<0) continue;
            int sum=change(coins,amount-coin,dp);
            if(sum>=0&&sum<min) {
              min=sum+1;
              //dp[amount-coin]=sum;
            }
            //if (dp[amount-coin]!=amount-coin+1) continue;//这一步是求不出来就continue
            //sum=Math.min(change(coins,amount-coin,dp)+1,dp[amount]) ;
        }
        dp[amount]=min==Integer.MAX_VALUE?-1:min;

        //if(dp[amount]==Integer.MAX_VALUE)return -1;
        return dp[amount];
    }
}
